package binarytree


type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// 让BST的值都在low,high之间    删除BST的题
// 错误，忽略了BST的结构
// func trimBST(root *TreeNode, low int, high int) *TreeNode {
// 	if root == nil {
// 		//边界 
// 		return root
// 	}
// 	if root.Val < low || root.Val > high {
// 		return nil   //删除这个节点  上一层丢失该点信息
// 	}
// 	root.Left = trimBST(root.Left, low,high)
// 	root.Right = trimBST(root.Right, low,high)
// 	return root
// }

func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		//边界 
		return nil
	}
	if root.Val < low {
		// 那么root左侧都是小于low的  所以只考虑右侧
		right := trimBST(root.Right,low,high)
		return right  // 返回上一层  删除这一层root
	}
	if root.Val > high {
		// 右侧都是大于high
		left := trimBST(root.Left, low,high)
		return left
	}
	root.Left = trimBST(root.Left, low,high)
	root.Right = trimBST(root.Right, low,high)
	return root
}
// 迭代
func trimBST1(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }
    // 处理 root，让 root 移动到[low, high] 范围内，注意是左闭右闭
    for root != nil && (root.Val<low||root.Val>high){
        if root.Val < low{
            root = root.Right
        }else{
            root = root.Left
        }
    }
    cur := root
    // 此时 root 已经在[low, high] 范围内，处理左孩子元素小于 low 的情况（左节点是一定小于 root.Val，因此天然小于 high）
    for cur != nil{
        for cur.Left!=nil && cur.Left.Val < low{
            cur.Left = cur.Left.Right
        }
        cur = cur.Left
    }
    cur = root
    // 此时 root 已经在[low, high] 范围内，处理右孩子大于 high 的情况
    for cur != nil{
        for cur.Right!=nil && cur.Right.Val > high{
            cur.Right = cur.Right.Left
        }
        cur = cur.Right
    }
    return root
}